package Tree;

import java.util.LinkedList;
import java.util.Queue;

//从上往下打印二叉树
public class PrintByDown {
	public static void printFromTopToBottom(TreeNode root) {
		if (root == null) {
			return;
		}
		// 要想从上往下打印二叉树，需要一个队列，依次扫描结点,然后是左右节点，将孩子放入队列中
		// 如果队列不空，就继续扫描左右结点
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while (!queue.isEmpty()) {
			// 将第一个元素出队
			TreeNode node = queue.poll();
			System.out.print(node.val + " ");
			if (node.left != null) {
				queue.add(node.left);
			}
			if (node.right != null) {
				queue.add(node.right);
			}
		}
	}

	public void printByLevel(TreeNode root){
		if(root == null){
			return;
		}
		int nextToBePrint = 1;
		int nextLevelNodes = 0;
		LinkedList<TreeNode> list = new LinkedList<>();
		TreeNode curNode = root;
		list.add(curNode);
		while (!list.isEmpty()) {
			curNode = list.removeFirst();
			nextToBePrint--;
			System.out.print(curNode.val + " ");
			if(curNode.left != null) {
				list.add(curNode.left);
				nextLevelNodes++;
			}
			if(curNode.right != null) {
				list.add(curNode.right);
				nextLevelNodes++;
			}
			if(nextToBePrint == 0){
				nextToBePrint = nextLevelNodes;
				nextLevelNodes = 0;
				System.out.println();
			}
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int a[] = { 10, 5, 3, 9, 21, 27, 36, 59, 42 };
		BinaryTreeCreate tree = new BinaryTreeCreate();
		for (int i = 0; i < a.length; i++) {
			tree.createBinaryTree(tree.root, a[i]);
		}
		printFromTopToBottom(tree.root);
	}
}
